package hehe.test;

public class BinaryST<Key extends Comparable<Key>, Value> {
	private Node root;
	private class Node {
		private Key key;
		private Value value;
		private Node left, right;
		private int N;
		
		public Node(Key key, Value value, int n) {
			super();
			this.key = key;
			this.value = value;
			N = n;
		}
	}
	public int size() {
		return size(root);
	}
	private int size(Node root) {
		if(root == null) return 0;
		else             return root.N;
	}
	public Value get(Key key) {
		return get(root, key);
	}
	private Value get(Node root, Key key) {
		if(root == null) {
			return null;
		}
		int cmp = key.compareTo(root.key);
		if(cmp < 0) return get(root.left, key);
		else if(cmp > 0) return get(root.right, key);
		else return root.value;
	}
	
	public void put(Key key, Value val) {
		root = put(root, key, val);
	}
	public Node put(Node x, Key key, Value val) {
		if(x == null) return new Node(key, val, 1);
		int cmp = key.compareTo(x.key);
		if(cmp < 0) {
			x.left = put(x.left, key, val);
		}
		else if(cmp > 0) {
			x.right = put(x.right, key, val);
		}
		else x.value = val;
		x.N = size(x.left) + size(x.right) + 1;
		return x;
	}
	public static void main(String[] args) {
	}
}
